<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Palindrome Partition</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="palindrome-partition">Palindrome Partition</h1>
<h1 id="1-palindrome-partition-列出所有的分割方案">1. Palindrome Partition 列出所有的分割方案</h1>
<ul>
<li>leetcode 131</li>
<li><a href="https://leetcode.com/problems/palindrome-partitioning/">https://leetcode.com/problems/palindrome-partitioning/</a></li>
</ul>
<h2 id="11-常规dfs解法">1.1 常规dfs解法</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition</span><span class="hljs-params">(self, s: str)</span> -&gt; List[List[str]]:</span>
        ans = []
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(s, ans, tmp)</span>:</span>
            <span class="hljs-keyword">if</span> s == <span class="hljs-string">""</span>:
                ans.append(tmp[:])
                
            n = len(s)
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> s[:i+<span class="hljs-number">1</span>] == s[:i+<span class="hljs-number">1</span>][::<span class="hljs-number">-1</span>]:
                    tmp.append(s[:i+<span class="hljs-number">1</span>])
                    _dfs(s[i+<span class="hljs-number">1</span>:], ans, tmp)
                    tmp.pop()
        _dfs(s, ans, [])
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="12-dp--bottom-to-top">1.2 dp , bottom to top</h2>
<p>dp[i] 表示 s[:i] 范围内的所有palindrome分割方案</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition</span><span class="hljs-params">(self, s)</span>:</span>
  
        n = len(s)
        <span class="hljs-keyword">if</span> n == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> [[]]
        
        dp = {<span class="hljs-number">0</span>:[[]], <span class="hljs-number">1</span>:[[s[<span class="hljs-number">0</span>]]]}
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
            dp[i+<span class="hljs-number">1</span>] = []
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i+<span class="hljs-number">1</span>):
                string = s[j:i+<span class="hljs-number">1</span>]
                <span class="hljs-keyword">if</span> string == string[::<span class="hljs-number">-1</span>]:
                    <span class="hljs-keyword">for</span> partition <span class="hljs-keyword">in</span> dp[j]:
                        dp[i+<span class="hljs-number">1</span>].append(partition+[string])
        <span class="hljs-keyword">return</span> dp[n]
</div></code></pre>
<h1 id="2-palindrome-partition-ii-寻找最小分割次数">2. Palindrome Partition II  寻找最小分割次数</h1>
<ul>
<li>leetcode 132</li>
<li><a href="https://leetcode.com/problems/palindrome-partitioning-ii/">https://leetcode.com/problems/palindrome-partitioning-ii/</a></li>
</ul>
<h2 id="21-dp-解法">2.1 dp 解法</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minCut</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        n = len(s)
        dp = [n] * (n+<span class="hljs-number">1</span>)
        dp[<span class="hljs-number">0</span>] = <span class="hljs-number">-1</span>        <span class="hljs-comment"># 初始值dp[0] = -1, 为了方便后面的计算</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i):
                <span class="hljs-keyword">if</span> s[j:i] == s[j:i][::<span class="hljs-number">-1</span>]:
                    dp[i] = min(dp[i], <span class="hljs-number">1</span> + dp[j])
                    
        <span class="hljs-keyword">return</span> dp[n]
</div></code></pre>
<h2 id="22-tushare-roy-解法">2.2 tushare roy 解法</h2>
<ul>
<li><a href="https://www.youtube.com/watch?v=lDYIvtBVmgo&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=26">https://www.youtube.com/watch?v=lDYIvtBVmgo&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=26</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/PalindromePartition.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/PalindromePartition.java</a></li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp15.png" alt="dp15.png"></p>
<p>下面是tushare roy提供的代码，好像和上面视频里面讲解的不一样啊. 倒是和2.1 的思路一致。</p>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCut</span><span class="hljs-params">(String str)</span></span>{
        <span class="hljs-keyword">if</span> (str.length() == <span class="hljs-number">0</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        }

        <span class="hljs-keyword">int</span>[] cut = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[str.length()];
        <span class="hljs-keyword">boolean</span> isPal[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">boolean</span>[str.length()][str.length()];
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; str.length(); i++) {
            <span class="hljs-keyword">int</span> min = i;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt;= i; j++) {
                <span class="hljs-keyword">if</span> (str.charAt(i) == str.charAt(j) &amp;&amp; (i &lt;= j + <span class="hljs-number">1</span> || isPal[i - <span class="hljs-number">1</span>][j + <span class="hljs-number">1</span>])) {
                    isPal[i][j] = <span class="hljs-keyword">true</span>;
                    min = Math.min(min, j == <span class="hljs-number">0</span> ? <span class="hljs-number">0</span> : <span class="hljs-number">1</span> + cut[j - <span class="hljs-number">1</span>]);
                }
            }
            cut[i] = min;
        }
        <span class="hljs-keyword">return</span> cut[str.length() - <span class="hljs-number">1</span>];
    }
</div></code></pre>
<p>尝试着用视频里面提供的思路来写写, 下面的结果应该是对的，但是会超时...</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minCut</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        n = len(s)
        dp = [[<span class="hljs-number">0</span>] * (n) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)]
        
        <span class="hljs-keyword">for</span> l <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n-l):
                j = i+l
                <span class="hljs-keyword">if</span> s[i:j+<span class="hljs-number">1</span>] == s[i:j+<span class="hljs-number">1</span>][::<span class="hljs-number">-1</span>]:
                    dp[i][j] = <span class="hljs-number">0</span>
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = n
                    <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(i, j):
                        dp[i][j] = min(dp[i][j], <span class="hljs-number">1</span> + dp[i][k] + dp[k+<span class="hljs-number">1</span>][j])
            
            <span class="hljs-comment">#print(f"l={l}")</span>
            <span class="hljs-comment">#pprint(dp,width=20)</span>
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">0</span>][n<span class="hljs-number">-1</span>]
</div></code></pre>

    </body>
    </html>